//
// Created by Administrator on 2021/11/3.
// May Saint Diana bless you!
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;
typedef pair<int, int> pii;

class Solution {
public:
    /**
    把每一个元素称作块。因为那个图片给的好像瓷砖啊。
    其实做这题一开始都是想的是对于每一个块，去找它四个方向最高的高度中的最小值(二维下则是左右最高的高度取较小的那一个)作为上界，当前块作为下界
    但是这4个方向每次遍历复杂度过高，且不能像二维那样去提前预存每个方向的最大值
    那可以反过来我不以每个块为处理单元，而是以块的四周作为处理单元
    那如何保证所有四周的可能性都考虑到呢？
    我们从矩阵的最外围往里面遍历，像一个圈不断缩小的过程
    为了防止重复遍历用visited记录
    其次要用小顶堆(以高度为判断基准)来存入所有快的四周(即圈是不断缩小的，小顶堆存的就是这个圈)
    为什么要用小顶堆？
    这样可以保证高度较小的块先出队
    为什么要让高度较小的块先出队？(关键点)
      1. 一开始时候就讲了基础做法是：对于每一个块，去找它四个方向最高的高度中的最小值(二维下则是左右最高的高度取较小的那一个)作为上界，当前块作为下界
      2. 而我们现在反过来不是以中心块为处理单元，而是以四周作为处理单元
      3. 我们如果能确保当前出队的元素对于该中心块来说是它周围四个高度中的最小值那么就能确定接雨水的大小
      4. 为什么队头元素的高度比中心块要高它就一定是中心块周围四个高度中的最小值呢？
         因为我们的前提就是小顶堆：高度小的块先出队，所以对于中心块来说，先出队的必然是中心块四周高度最小的那一个
    步骤：
      1. 构建小顶堆，初始化为矩阵的最外围(边界所有元素)
      2. 不断出队，倘若队头元素的四周(队头元素的四周其实就是上面说的中心块，队头元素是中心块的四周高度中最矮的一个)
         即代表能够接雨水：队头元素减去该中心块即当前中心块能接雨水的值
      3. 但是接完雨水之后中心块还要存进队列中，但这时要存入的中心块是接完雨水后的中心块
    */
    int trapRainWater(vector<vector<int>> &heightMap) {
        // 至少3行3列
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) {
            return 0;
        }
        int m = (int) heightMap.size();
        int n = (int) heightMap[0].size();
        priority_queue<pii, vector<pii>, greater<pii>> pq; // 小根堆
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) { // 边界点
                    pq.push({heightMap[i][j], i * n + j}); // 高度和全局序列
                    visit[i][j] = true; // 访问标记
                }
            }
        }

        int res = 0;
        int dirs[] = {-1, 0, 1, 0, -1};
        while (!pq.empty()) {
            pii curr = pq.top(); // 弹出栈顶，即最小的那个高度
            pq.pop();
            for (int k = 0; k < 4; ++k) { // 遍历四周
                int nx = curr.second / n + dirs[k];
                int ny = curr.second % n + dirs[k + 1];
                // 以nx,ny为中心块 栈顶是这个中心块四周最小的
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visit[nx][ny]) {
                    if (heightMap[nx][ny] < curr.first) { // 若新块比栈顶块的高度小
                        res += curr.first - heightMap[nx][ny];
                    }
                    visit[nx][ny] = true;
                    pq.push({max(heightMap[nx][ny], curr.first), nx * n + ny}); // 更新为接完水的高度
                }
            }
        }
        return res;
    }

    /**
     * bfs解法
     * @param heightMap
     * @return
     */
    int trapRainWater2(vector<vector<int>> &heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        int maxHeight = 0;
        int dirs[] = {-1, 0, 1, 0, -1};
        // 找到全局最大值
        for (int i = 0; i < m; ++i) {
            maxHeight = max(maxHeight, *max_element(heightMap[i].begin(), heightMap[i].end()));
        }
        vector<vector<int>> water(m, vector<int>(n, maxHeight)); // 方块接水后的高度
        queue<pair<int, int>> qu;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) { // 边界点无法储水，接水后的高度还是原始高度
                    if (water[i][j] > heightMap[i][j]) {
                        water[i][j] = heightMap[i][j];
                        qu.push(make_pair(i, j));
                    }
                }
            }
        }
        while (!qu.empty()) {
            // 出队
            int x = qu.front().first, y = qu.front().second;
            qu.pop();
            for (int i = 0; i < 4; ++i) { // 遍历四周
                int nx = x + dirs[i], ny = y + dirs[i + 1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) { // 出界
                    continue;
                }
                //当前方块 (i,j) 的接水高度 water[i][j] 小于与它相邻的 4个模块的接水高度时，
                // 则我们将进行调整接水高度，我们将其相邻的四个方块的接水高度调整与 (i,j) 的高度保持一致
                if (water[x][y] < water[nx][ny] && water[nx][ny] > heightMap[nx][ny]) {
                    water[nx][ny] = max(water[x][y], heightMap[nx][ny]);
                    qu.push(make_pair(nx, ny));
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res += water[i][j] - heightMap[i][j]; // 最后的答案为  接水后的高度减去接水前的高度
            }
        }
        return res;
    }

};


int main() {
    vector<vector<int>> heightMap{{1, 4, 3, 1, 3, 2},
                                  {3, 2, 1, 3, 2, 4},
                                  {2, 3, 3, 2, 3, 1}};
    Solution solution;
    cout << solution.trapRainWater(heightMap) << endl;
    return 0;
}
